perm filename GLOS[DIS,DBL] blob
sn#229976 filedate 1976-08-08 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00004 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 .ASEC(Glossary of Technical Terms)
C00004 00003 . ASSEC(Glossary of Math Terms)
C00015 00004 . ASSECP(Glossary of AI Terms)
C00034 ENDMK
C⊗;
.ASEC(Glossary of Technical Terms)
<<Go through thesis, dumping terms into the glossary>
The "jargon" of a field facilitates communication among practitioners
of that field, but it too often excludes novices. I have tried to
soften the impact of each "buzz-word" when it was first used, but the
reader may need to frequently refresh his memory about the meanings
of certain terms.
This glossary is divided into two sections. The first contains
primarily Mathematics terms, strangely biassed because it just covers
what is referenced in this thesis. The second glossary, of Computer
Science and Artificial Intelligence terms, suffers from the same
tunnel vision. They may suffice for reading this document, but they
are certainly ⊗4not⊗* meant to be used for more general purposes.
.GLOS: ASECNUM ;
. ASSEC(Glossary of Math Terms)
.GLOS1P: PAGE;
.BEGIN TURN ON "↑↓_" TURN OFF "{}" SELECT 1
Abduction: In logic, a syllogism of the form "from A, conclude that
B is probably true". If your mental frame for an automobile contains
a hundred necessary features, and you see something satisfying only 90 of them,
you
can ⊗4abductively⊗* conclude it is probably an automobile.
Cardinality: the concept of "number". Two sets are of the same
cardinality iff they have the same number of elements.
Composition of two relations R and S: This is a new relation denoted
R⊗7o⊗*S, and defined as R⊗7o⊗*S(x) = R(S(x)). So R⊗7o⊗*S maps
elements of the domain of S into elements of the range of R. Notice
that if R and S are both functions, then so is R⊗7o⊗*S. The intuitive
picture of this process is to operate on x with the relation S, and
⊗4then⊗* apply R to the results.
Function: an operation f which associates, to each element x of some
set D, an element f(x) of some set R. D and R are the domain and
range of f. Notice that a function may be considered a special kind
of relation.
For a ⊗4relation⊗* f (on DxR) to be called a ⊗4function⊗*, f must satisfy two
important constraints: (i) it must be always-defined on its domain; that is,
for all domain elements x⊗6ε⊗*D, f(x) must exist. (ii) f must be single-valued;
that is, f(x) must be a singleton.
Iff: if and only if; implies and is implied by; is equivalent to; ⊗8<==>⊗*.
Integers: positive and negative whole numbers; i.e. ...,-2, -1, 0, 1,
2,...
Map: used as a verb, this word indicates the action of applying a
function or a relation; e.g., we say that ⊗4squaring⊗* maps 7 into
49. Used as a noun, it is a synonym for function.
Mathematical concept: this is taken to mean all the constructions,
definitions, conjectures, operations, structures, etc. that a
mathematician deals with. Some examples: Set-intersection, Sets, The
unique factorization theorem, every entry listed in this glossary.
Mathematical intuition: this is the mental imagery which can be
brought to bear. Typically, we transform the situation to an
abstract, simplified one, manipulate it there, and re-translate the
results into the original notation. For example, our intuition about
"ordering" may involve the image of marks on a yardstick. We can then
answer questions involving ordering rapidly, using this
representation. Three features of the intuitive image should be
noted: (i) it is typically fast and simple, (ii) it is opaque, one
cannot introspect too easily on "why it works", and (iii) it is
fallible, occasionally leading to wrong results.
Mathematical research: The fundamental idea here is that mathematics
is an ⊗4empirical⊗* science, just as much as chemistry or physics.
In doing research, the ultimate goal is the creation of new,
interesting theories, but the techniques used include looking for
patterns in empirical data, inducing new conjectures, modelling some
aspects of the real world, etc. Although the final product looks like
a smooth, formal development, magically flowing from postulates to
lemmas to theorems, the actual research process involved untold blind
alleys, rough guesses, and hard work. (Analogy: The process of
painting is rarely itself artistic.)
Mathematical theory: to qualify as a theory, we must have (i) a basis
of undefined primitive terms, (ii) definitions involving these, (iii)
axioms involving all the primitives and defined terms (iv)
conjectures and theorems relating these terms. To be at all
worthwhile, however, the theory must also meet the fuzzy requirements
that (v) there is some correspondence between the primitives and some
"real-world" concepts, between the axioms and some "real"
relationships, and (vi) some of the theorems are unexpected, hard to
prove, elegant, interesting, etc.
Mersenne prime: a prime number which happens to be of the form 2↑p-1,
where p is prime.
Natural numbers: non-negative integers; i.e., 0, 1, 2, 3,...
No.: an abbreviation for "Number".
Number: in the typical loose fashion of computer scientists, I intend
this to mean a non-negative integer: i.e., a ⊗4natural⊗* number.
Ordering: the concept of "before" and "after". This distinguishes a
list from a bag (multiset). The formal axioms for ordering simply
state the obvious properties of the intuitive image of a list.
Prime numbers: natural numbers which have no divisors other than 1
and themself; e.g., 17, but ⊗4not⊗* 15 (=3x5). Primes are interesting
because of the myriad times they crop up in diverse theorems -- from
the Chinese Remainder Theorem (solving systems of linear congruence
equations), to the Law of Quadratic Reciprocity, to Fermat's Theorem
(for all integers n, for all primes p, n↑p is congruent to n (mod
p)). The "secret" of their value lies in the fact that all integers
can be factored ⊗4uniquely⊗* into a set of prime divisors. This
"Unique Factorization Theorem" lets us reduce questions about
integers to questions about primes.
Prime pairs: two prime numbers whose difference is two; e.g., 17 and 19.
Relation: an operation which associates, for each element of some set
D, a set of elements E = {e↓1, e↓2,...} of some set R. D and R are
the domain and range of the relation. For example, the relation
"⊗6≤⊗*" associates to 5 the set of numbers {5, 6, 7, 8,...} -- i.e.,
all integers which 5 is less than or equal to. The domain and range
of this relation are the integers.
Set-theoretic: having to do (in the context of this thesis) with
elementary finite set theory, and the primitive notions of mathematics
(e.g., union, insert, predicate, conjecture).
Unity: a fancy way of referring to the natural number "1".
⊗6|⊗*: The relation "divides-evenly-into". Thus we say 2|6.
⊗6α¬⊗*: The operation of negation. "⊗6α¬⊗*X" is read as "not X".
⊗6∨⊗*: Disjunction. "A⊗6∨⊗*B" is read as "A or B".
⊗6∧⊗*: Conjunction. "A∧B" is read as "A and B".
⊗6α⊗⊗*: Exclusive or. "Aα⊗B" is read as "A or B, but not both".
.SELECT 1;
⊗6α→⊗*: Implication. "Aα→B" is read as "If A then B".
⊗6α↔⊗*: Logical equivalence. "Aα↔B" is read as "A if and only if B".
⊗6α∀⊗*: Universal quantification. "⊗6α∀⊗*X" is read as "For all X".
⊗6α∃⊗*: Existential quantification. "α∃X" is read as "For some X".
. ASSECP(Glossary of AI Terms)
ACTORs: A modular form of representation, useful for distributing of
the task of ⊗4control⊗* among several components in a computer
program. Each ACTOR is a black box, with no parts or slots, but which
does have some assertions (a "contract") which he must honor. It
merely responds to a fixed set of messages, by sending out certain
messages of his own. These are delivered via a bureaucracy. See
[Hewitt 76].
AI: an abbreviation for Artificial Intelligence.
Bag: A bag is a kind of list structure, a bunch of elements which
are unordered, but one in which multiple copies of the same element
are permitted. One may visualize a paper bag filled with cardboard
letters. Technically, we shall say that a set is ⊗4not⊗* considered
to be a bag. A bag is denoted by enclosure within parentheses, just
as sets are within braces. So the bag containing X and four Y's might
be written (X Y Y Y Y), and would be considered indistinguishable
from the bag (Y Y Y X Y).
BEINGs: A modular form of representation of knowledge, conceived as a
collection of cooperating experts. Each expert is modelled by one
module, which consists of a list of Question/Answering-program pairs.
The set of questions is fixed for all the Beings in the system. When
any Being has a question, he broadcasts it to the entire system, and
some Being who recognizes it will take over control and try to answer
it by running ⊗4his⊗* appropriate Answering-program. In the process
of running this, some new questions may arise. Notice that Beings
distribute responsibility for control and for static knowledge. See
[Lenat 75b].
Bug: a flaw in a computer program. As Corey Sacerdoti put it, a bug refers to
something which is broken but not badly.
Concept: within the context of this document, the word "concept" typically
refers to a precise frame-like data structure, a BEING. Semantically, each concept
is meant to correspond to one abstract entity that we would intuitively
call a concept: an object, an operator, a conjecture, etc. See "facet".
Cooperating Knowledge Sources: Very often, in tackling a problem, one
receives some hints and some constraints from very different sources,
phrased in very different languages, often addressing different
representations of the problem. For example, in trying understand a
human speaker, our memory of the previous discussion and knowledge of
the speaker may narrow down the possible ⊗4meanings⊗* of what he is
saying. Our ears, of course, register the precise acoustic wave-forms
he is uttering. Our English vocabulary forces us to interpret
imperfect signals as real words. Our eyes see his gestures and his
lip movements, and give us more information. All these different
sources of information must be used, and yet they all are talking in
different "languages" to us. The most trivial solution is to keep
all the sources independent, and keep working until one of them can
solve the problem all by itself. A much better solution is to
transform all their babblings into one canonical representation, one
single language. This way, all the knowledge sources can cooperate.
Coupled: two functional subsystems are causally connected; one
influences the other. See the entry for "Linear".
CPU time: Central-Processing-Unit runtime (cpu time) is the number of
execution cycles of the computer that the AM program has used up.
This is conveniently measured in seconds, minutes, and hours, where
one cpu minute is the amount of processing done in one minute of real
time, when AM has 100% of the machine, and is runninng without any
input or output.
CS: an abbreviation for Computer Science.
Execution: a program is actually used by ⊗4running⊗* it on a particular
set of input data. This process is known as program ⊗4execution⊗*.
Facet: Within the context of this document, the word "facet" denotes a
slot of the kind of data-structure known as "concepts" (qv).
Thus "⊗4a facet of the Compose concept⊗*" really just means a slot of a
particular frame, a part of certain BEING,
one single attribute/value pair taken from the property list of the Lisp
atom named Compose.
Semantically, each facet holds information
pertaining to a single aspect of the concept it is a part of; hence the
suggestive name: "facet".
FRAMEs: A modular representation of knowledge. Each module is a list
of Feature/Value pairs. The ⊗4value⊗* represents a default assumption
which can be relied on until/unless new information comes in about
that feature. Each frame has whatever ⊗4features⊗* (called "slots")
seem appropriate. Whenever a situation S is encountered, the
frame(s) for S are activated. As new information rolls in, it
replaces the default information in various slots. Notice the
emphasis on distributing static knowledge (⊗4data⊗*), not necessarily
control, in such a system. See [Piaget 55] or [Minsky 75].
Function: a small, executable part of a program. When fed the proper kind of
argument(s), a function will "run" and ultimately produce some sort of value.
Unlike pure mathematical functions (see the previous glossary), a Lisp function
can have side effects (qv).
Garbage collection: As a Lisp program executes, various list structures (pointer
networks) are created. When the last pointer to a structure is removed, that
structure has essentially been irretrievably forgotten. If the operating
system knew which storage cells were thus "free", it could re-cycle them,
reuse them. The process of finding and liberating such discarded lists is called
garbage collection. This is performed automatically by the Lisp language,
whenever space is almost all filled up.
Hack: A quick job that produces what is needed, but
not well. Introducing a heuristic which was only used once, in a predetermined
way (e.g., to fix a particular bug), would be a real hack.
Hand-crafting: the human programmer carefully designs his system in
such a way that the pieces just manage to mesh. For instance: he
provides just the perfect set of axioms so that his theorem-prover
can solve a certain problem, or he modifies the program's strategies
so that they efficiently manipulate the axiom set in just the right
way.
Heterarchy: A kind of control structure for a computer program which
is distinct from hierearchy. Heterarchical structuring views the
whole program as a collection of equal partners, an unstructured set
of functions. "Control" is viewed as a spotlight, which can be
flicked from one function to another. The functions can affect who
does or doesn't get control next, but there is no guarantee who will
get control, or that control will revert back to some function which
once had it. Aside from the lure of its democratic flavor, it is
clearly a natural way to represent cooperating knowledge modules.
Hierarchy: This term refers to a kind of control structure for a
computer program. The typical hierarchical structure is one in which
a function calls a subroutine, which processes and then returns a
value to that function. A program is viewed as a tree structure,
with lines indicating "calling".
Interact: a dynamic mode of communication between a human and a computer
program. The human reacts to what the program is printing out on his terminal,
and the program in turn reacts to what the user types in. This may take the
form of questioning and answering, or interrupting and commenting.
Interestingness: Note that this is not a valid English word. In the context of
AM, it refers to a numeric value, computed by little Lisp programs stored in
the "Interest" facets of various concepts. Despite the danger of imbuing such
a humble scheme with all the mystique of what is and isn't interesting,
it is felt that a sufficient component of that evaluation has been captured
to warrant the name. Pragmatically, it is of much more use to the user to
see "Interestingness of Compose has just risen" than to see a message like
"G00034 incremented".
Kludge (or Kluge): This is a program feature which is an unfair shortcut
around a specific problem. One "kludgy" way of improving the
algorithm of a given concept is to ask the user for a better algorithm.
Linear: a system whose components, inputs, and outputs
⊗4superimpose⊗* -- i.e., don't couple.
Lisp: a ↓_LIS_↓t-↓_P_↓rocessing programming language. Primitive operations exist for
manipulating nested list structures. Since Lisp functions are also merely lists,
it is easy to create and modify entities which are then executed (qv).
Modular Representations of Knowledge in AI Systems: Knowledge is
partitioned into packets (called modules, frames, units, productions,
Beings, experts, Actors) along lines of: different applicabilities,
expertise, purpose, importance, generality, etc. Each packet is
structurally similar to all the rest. Advantages: By having the
knowledge discretized, pieces can be added and/or removed with no
trouble. The knowledge of the system is easily inspected and
analyzed. The structural similarity yields several advantages: a
simple control system suffices to "run" all the knowledge, the
modules can intercommunicate easily, new modules can be inserted
without knowing precisely "who else" is already in the system. In
general, the less similarly-structured the modules are, the simpler
the inter-communication media must be. Modular representation is a
natural way to implement cooperating knowledge sources.
Number: in the typical loose fashion of computer scientists, I intend
this to mean a non-negative integer: i.e., a ⊗4natural⊗* number.
.OPENDP: PAGE;
Open research problem: a limitation of the AM system.
Recur: Often, part of a definition will refer back to that very same
definition. This may lead to an infinite circular loop, or it may
terminate. The following definition of "is larger than" is recursive,
because the last line recurs:
.WBOX(15,15)
MBOX set R ⊗4is larger than⊗* set S $
MBOX if R={} but S≠{}, or $
MBOX if neither is empty and $
MBOX Remove-element(R) ⊗4is larger than⊗* Remove-element(S). $
.EBOX
Recurse: a transitive verb which means "to swear again." It must be
distinguished from "recur", above.
Side effects: while a function is executing, it may cause changes in the state of
its environment which persist even after the function has returned a value. This is
like hysteresis effects. For example, a function may create or destroy some list
structure, define a new function, reset some variable, etc.
Such activities are called side effects of the function.
Space: The memory of a computer is quite finite. Though it may be supplemented
by slow auxilliary devices (tapes, discs, etc.), the actual number of storage
cells in the computer's fast "core" memory is a limiting factor in program
behavior. Storage space, or just "space", refers to these internal memory
cells. When space is exhausted, the only remedy is to perform a garbage
collection (qv).
System: this can mean a computer program, and occasionally is just an
another way of referring to AM. In general, a system is any
collection of entities related to form a meaningful whole.
Terminal: a communications device for passing information between a computer
system and a human. This could be a teletype, a TV screen and keyboard, etc.
The terminal is usually portable and remotely located from the computer.
User: the human being who sits at a computer terminal and watches AM run
(occasionally, perhaps, interacting with AM).
.END